#include "graphMatrix.h"


PGraphMatrix createGraph(int n, AdjType **ajt)
{
    PGraphMatrix graph;
    int i, j;
    
    if (n < 0 || ajt == NULL)
    { 
        return NULL;
    }

    graph = (PGraphMatrix) malloc(sizeof(struct GraphMatrix));
    
    if (graph == NULL)
    {
        return NULL;
    }
    
    graph->n = n;
    graph->vexs = (struct Vertex *) malloc(sizeof(struct Vertex)*n);
    
    if (graph->vexs == NULL)
    { 
        free(graph);
        return NULL;
    }

    for (i = 0; i < n; i++)
    {
        graph->vexs[i].v = 'a'+i;
        graph->vexs[i].index = i;
        graph->vexs[i].visit = 0;      
    }

   graph->arcs = (AdjType **) malloc(sizeof(AdjType *)*n);

   for (i = 0; i < n; i++)
   {
       graph->arcs[i] = (AdjType *) malloc(sizeof(AdjType)*n);
   }
   
   for (i = 0; i < n; i ++)
   {
       for (j = 0; j < n; j++)
       {
          graph->arcs[i][j] = ajt[i][j]; 
       }
   }

   return graph;
}

int isNullGraph(PGraphMatrix graph)
{
    return graph == NULL;
}

PVertex firstVertex(PGraphMatrix graph)
{
	if (isNullGraph(graph))
	{
		return NULL;
	}

	return &(graph->vexs[0]);
}

PVertex nextVertex(PGraphMatrix graph, PVertex vi)
{
	int index, i;

	if (isNullGraph(graph) || vi == NULL)
	{
		return NULL;
	}

	index = vi->index;

	if (index < graph->n - 1)
	{
		return &(graph->vexs[index+1]);
	}

	return NULL;
	/*
	for (i = 0; i < graph->n; i++)
	{
		if (graph->arcs[index][i] != 0)
		{
			next = i;
			return &(graph->vexs[i]);
		}
	}
	*/

	return NULL;
}

PVertex findVertex(PGraphMatrix graph, VexType value)
{
	int i;

	if (isNullGraph(graph))
	{
		return NULL;
	}

	for (i = 0; i < graph->n; i++)
	{
		if (graph->vexs[i].v == value)
		{
			return &(graph->vexs[i]);
		}
	}

	return NULL;
}

int hasVertex(PGraphMatrix graph, PVertex vi)
{
	int i;

	if (isNullGraph(graph) || vi == NULL)
	{
		return -1;
	}

	for (i = 0; i < graph->n; i++)
	{
		if (vi == &(graph->vexs[i]))
		{
			return 1;
		}
	}

	return -1;
}


int deleteEdge(PGraphMatrix graph, PVertex vi, PVertex vj)
{
	int index_vi, index_vj;

	if (isNullGraph(graph) || vi == NULL || vj == NULL
		|| !hasVertex(graph, vi) || !hasVertex(graph, vj))
	{
		return -1;
	}

	index_vi = vi->index;
	index_vj = vj->index;

	if (graph->arcs[index_vi][index_vj] == 1 
		&& graph->arcs[index_vj][index_vi] == 1)
	{
		graph->arcs[index_vi][index_vj] = 0;
		graph->arcs[index_vj][index_vi] = 0;
		return 1;
	}

	return 0;
}

int addEdge(PGraphMatrix graph, PVertex vi, PVertex vj)
{
	int index_vi, index_vj;

	if (isNullGraph(graph) || vi == NULL || vj == NULL
		|| !hasVertex(graph, vi) || !hasVertex(graph, vj))
	{
		return -1;
	}

	index_vi = vi->index;
	index_vj = vj->index;

	if (graph->arcs[index_vi][index_vj] == 0 
		&& graph->arcs[index_vj][index_vi] == 0)
	{
		graph->arcs[index_vi][index_vj] = 1;
		graph->arcs[index_vj][index_vi] = 1;
		return 1;
	}

	return 0;
}

int findEdge(PGraphMatrix graph, PVertex vi, PVertex vj)
{
	int index_vi, index_vj;

	if (isNullGraph(graph) || vi == NULL || vj == NULL
		|| !hasVertex(graph, vi) || !hasVertex(graph, vj))
	{
		return -1;
	}

	index_vi = vi->index;
	index_vj = vj->index;

	if (graph->arcs[index_vi][index_vj] == 1 
		&& graph->arcs[index_vj][index_vi] == 1)
	{
		return 1;
	}

	return 0;
}

PVertex firstAdjacent(PGraphMatrix graph, PVertex vi)
{
	int index, i;

	if (isNullGraph(graph) || vi == NULL)
	{
		return NULL;
	}

	index = vi->index;

	for (i = 0; i < graph->n; i++)
	{
		if (graph->arcs[index][i] != 0)
		{
			return &(graph->vexs[i]);
		}
	}

	return NULL;
}

PVertex nextAdjacent(PGraphMatrix graph, PVertex vi, PVertex vj)
{
	int i;
	int index_vi, index_vj;

	if (isNullGraph(graph) || vi == NULL || vj == NULL
		|| !hasVertex(graph, vi) ||!hasVertex(graph, vj))
	{
		return NULL;
	}

	if (findEdge(graph, vi, vj))
	{
		//BUG : what if the return value PVertex is equal to vj?
		//return nextVertex(graph, vi);
		index_vi = vi->index;
		index_vj = vj->index;

		for (i = index_vi; i < graph->n; i++)
		{
			if (graph->arcs[index_vj][i] == 1 
				&& i != index_vi)
			{
				return &(graph->vexs[i]);
			}
			
		}
	}

	return NULL;
}

int print(PGraphMatrix graph)
{
    int i, j;

    if (isNullGraph(graph))
    {
        return -1;
    }

    printf("  ");
    for (i = 0; i < graph->n; i++)
    {
        printf("%c ", graph->vexs[i].v);
    }

    printf("\n");

    for (i = 0; i < graph->n; i++)
    {
        printf("%c ", graph->vexs[i].v);
        for (j = 0; j < graph->n; j++)
        {
            printf("%d ", graph->arcs[i][j]);
        }
        printf("\n");
    }   
    
    return i;
}

int printVertex(PGraphMatrix graph, PVertex vi)
{
	int i;

	if (isNullGraph(graph) || vi == NULL)
	{
		return -1;
	}

	for (i = 0; i < graph->n; i++)
	{
		if (vi == &(graph->vexs[i]))
		{
			printf("\n========Vertex========\n");
			printf("vertex node = %c\n", vi->v);
			printf("vertex index = %d\n", vi->index);
			printf("vertex visited = %d\n\n", vi->visit);
			break;
		}
	}

	return 1;
}

void dftGraph(PGraphMatrix graph)
{
	PVertex v;

	if (isNullGraph(graph))
	{
		return ;
	}

	for (v = firstVertex(graph); v != NULL; v = nextVertex(graph, v))
	{
		if (v->visit != 1)
		{
			dfsGraph(graph, v);
		}
	}

	printf("\n");
}

void dfsGraph(PGraphMatrix graph, PVertex vi)
{
	PVertex v;

	if (isNullGraph(graph))
	{
		return ;
	}

	vi->visit = 1;
	printf("%c ", vi->v);
	//printf("CURRENT FIRST VERTEX IS %c\n", vi->v);

	for (v = firstAdjacent(graph, vi); v != NULL; 
			v = nextAdjacent(graph, v, vi))
	{
		if (v->visit != 1)
		{
			//printVertex(graph, vi);
			//printVertex(graph, v);
			//printf("%c -> %c\n", vi->v, v->v);
			dfsGraph(graph, v);
		}
	}

}

int destroyGraph(PGraphMatrix *graph)
{
	int i;
	if (isNullGraph(*graph))
	{
		return -1;
	}

	if ((*graph)->vexs != NULL)
	{
		free((*graph)->vexs);
		(*graph)->vexs = NULL;
	}
	
	for (i = 0; i < (*graph)->n; i++)
	{
		if ((*graph)->arcs[i] != NULL)
		{
			free((*graph)->arcs[i]);
		}
	}

//	free((*graph)->arcs);
	free(*graph);
	*graph = NULL;
	
	return 1;
}
